package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

/**
 * lixw
 * 2021/11/9
 **/
public class SubtreeAnotherTree572 {


    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }

    private boolean dfs(TreeNode root, TreeNode node) {
        if (root == null) return node == null;
        return isSame(root, node) || dfs(root.left, node) || dfs(root.right, node);
    }

    private boolean isSame(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null) {
            return true;
        }
        if (r1 == null || r2 == null) return false;
        return r1.val == r2.val && isSame(r1.left, r2.left) && isSame(r1.right, r2.right);
    }
}
